package com.hardy.basic;

import java.util.*;

/**
 * Author: Hardy
 * Date:   2021/2/3
 * Description:
 **/
public class Num {

    // 440. 字典序的第K小数字
    int findKthNumber(int n, int k) {
        int cur = 1;
        k--;
        while (k > 0) {
            int s = culStep(n, cur, cur + 1);
            if (s <= k) {
                k -= s;
                cur += 1;
            } else {
                k -= 1;
                cur *= 10;
            }
        }
        return cur;
    }

    // n范围: n1 -> n2 需要经历都少节点
    int culStep(int n, int n1, int n2) {
        int step = 0;
        for (; n1 <= n; n1 *= 10, n2 *= 10) {
            step += Math.min(n2, n + 1) - n1;
        }
        return step;
    }

    // 打印字典序
    List<Integer> printKthNumber(int n) {
        List<Integer> list = new LinkedList<>();
        for (int i = 1; i <= 9; i++) {
            if (i > n) break;
            collect(i, n, list);
        }
        return list;
    }

    void collect(int i, int n, List<Integer> list) {
        list.add(i);
        if (i == n) return;
        for (int j = 0; j <= 9; j++) {
            if (i * 10 + j > n) break;
            collect(i * 10 + j, n, list);
        }
    }

    int rand10() {
        int rand = 0;
        while((rand = (rand7() - 1) * 7 + rand7()) <= 40) break;
        return rand % 10 + 1;
    }

    int rand7() {
        return 0;//rand7()
    }

    public static void main(String[] args) {
        Num main = new Num();

        //main.findKthNumber(2, 2);
        //main.findKthNumber(10, 2);
        //main.findKthNumber(13, 3);

        List<Integer> list = main.printKthNumber(28);
        System.out.println(Arrays.toString(list.toArray()));
    }
}
